package com.demo.algorithm.dfs02;

/**
 * Description: 回溯算法——N皇后
 *
 * @Date: 2021/4/30 23:59
 * @Author: zsyoung@qq.com
 */
public class NQueen {
//    private static Vector<Vector<String>> res;
//
//    /* 输⼊棋盘边⻓ n，返回所有合法的放置 */
//    Vector<Vector<String>> solveNQueens(int n) {
//        // '.' 表⽰空，'Q' 表⽰皇后，初始化空棋盘。
//        Vector<String> board (n, String(n, '.'));
//        backtrack(board, 0);
//        return res;
//    }
//
//    // 路径：board 中⼩于 row 的那些⾏都已经成功放置了皇后
//    // 选择列表：第 row ⾏的所有列都是放置皇后的选择
//    // 结束条件：row 超过 board 的最后⼀⾏
//    void backtrack(Vector<String> board, int row) {
//        // 触发结束条件
//        if (row == board.size()) {
//            res.add(board);
//            return;
//        }
//        int n = board[row].size();
//        for (int col = 0; col < n; col++) {
//            // 排除不合法选择
//            if (!isValid(board, row, col))
//                continue;
//            // 做选择
//            board[row][col] = 'Q';
//            // 进⼊下⼀⾏决策
//            backtrack(board, row + 1);
//            // 撤销选择
//            board[row][col] = '.';
//
//        }
//    }
//
//    /* 是否可以在 board[row][col] 放置皇后？ */
//    boolean isValid(Vector<String> board, int row, int col) {
//        int n = board.size();
//        // 检查列是否有皇后互相冲突
//        for (int i = 0; i < n; i++) {
//            if (board[i][col] == 'Q')
//                return false;
//        }
//        // 检查右上⽅是否有皇后互相冲突
//        for (int i = row - 1, j = col + 1;
//             i >= 0 && j < n; i--, j++) {
//            if (board[i][j] == 'Q')
//                return false;
//        }
//        // 检查左上⽅是否有皇后互相冲突
//        for (int i = row - 1, j = col - 1;
//             i >= 0 && j >= 0; i--, j--) {
//            if (board[i][j] == 'Q')
//                return false;
//        }
//        return true;
//    }
}
